/**
 * 剪绳子
 * 用两种方法实现
 * Created by JiaJia on 2019/6/30 0030.
 */
public class Code14 {
    public static void main(String[] args) {
        int n=10;
        System.out.println(cutRope1(n));
        System.out.println(cutRope2(n));
    }
    private static int cutRope1(int n){
        if (n < 2)
            return 0;
        if (n == 2)
            return 1;
        if (n == 3)
            return 2;
        int timesOf3 = n / 3;
        if (n - timesOf3 * 3 == 1)
            timesOf3--;
        int timesOf2 = (n - timesOf3 * 3) / 2;
        return (int) (Math.pow(3, timesOf3)) * (int) (Math.pow(2, timesOf2));
    }
    private static int cutRope2(int n){
        int[] dp=new int[n+1];
        dp[1]=1;
        for (int i = 2; i <=n ; i++) {
            for (int j = 1; j <i ; j++) {
                dp[i]=Math.max(dp[i],Math.max(j*(i-j),dp[j]*(i-j)));
            }
        }
        return dp[n];
    }
}